package com.justnow.offer;

public class Solution33 {
    public boolean verifyPostorder(int[] postorder) {
        if (postorder.length <= 0)
            return true;
        return recur(postorder, 0, postorder.length - 1);
    }

    private boolean recur(int[] postorder, int head, int tail) {
        if (head >= tail)
            return true;
        int tmp = head;
        while(postorder[tmp] < postorder[tail]) tmp++;//此时tmp为数组中第一个大于根节点值得元素的下标
        int rootIndex = tmp;
        while (postorder[tmp] > postorder[tail]) tmp++;//如果后面的值都大于根节点得值，那么最后tmp应该与tail相等。
        if (tmp != tail)
            //判断是否相等，如果不相等的话，说明并不符合后序遍历的要求
            return false;
        boolean chargeLeft = recur(postorder, head, rootIndex - 1);
        boolean chargeRight = recur(postorder, rootIndex, tail - 1);
        return chargeLeft && chargeRight;
    }

    public static void main(String[] args) {
        Solution33 solution33 = new Solution33();
        int[] array = {1, 3, 2, 6, 5};
        boolean b = solution33.verifyPostorder(array);
        System.out.println(b);
    }
}
